package com.example.leetcode.double_pointer;

class Solution_69 {
    public static void main(String[] args) {
        Solution_69 solution_69=new Solution_69();
        int i = solution_69.mySqrt(8);

    }

    public int mySqrt(int x) {
        if(x == 0 ){
            return x;
        }
        int left = 1;
        int right = x;
        int mid;

        while(left <= right){
            //为什么这样来求中值呢?
            //因为比如：1 2 3 4 5 6 7 8  我想求5 6 7 8这一段的中值
            //那么肯定等于1 2 3 4这一段加上5 6
            mid = left + (right - left)/2;

            //表示一个数的平方等于x
            //找到了
            if(mid == x / mid){
                return mid;
                //mid > x/mid
                //表示一个数的平方大于x
                //说明下一轮搜索区间是 [left..mid - 1]
            }else if(mid > x / mid){
                right = mid - 1;
                //表示一个数的平方小于x
                //说明下一轮搜索区间是 [mid+1..right]
            }else if(mid < x / mid){
                left = mid + 1;
            }
        }
        return right;
    }
}